package com.cuz.daileetcode;

/**
 *
 * 岛问题
 *
 * 一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右
 * 四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个
 * 矩阵中有多少个岛？
 * 举例：
 0 0 1 0 1 0
 1 1 1 0 1 0
 1 0 0 1 0 0
 0 0 0 0 0 0
 这个矩阵中有三个岛。
 *
 */
public class Day39 {
    /****
     * 返回岛屿数
     * @param m 二维描述
     * @return int
     */
    public static int countIslands(int[][] m) {
        // baseCase
        if (m == null || m[0] == null) {
            return 0;
        }
        //行
        int col = m.length;
        //列
        int row = m[0].length;
        //结果
        int res = 0;
        //遍历数组
        for (int i = 0; i < col; i++) {
            for (int j = 0; j < row; j++) {
                //如果是岛
                if (m[i][j] == 1) {
                    //结果加1
                    res++;
                    //从当前位置开始感染
                    infect(m, i, j);
                }
            }
        }
        return res;
    }


    /****
     *感染
     * @param arr 二维数组
     * @param col 行
     * @param row 列
     */
    private static void infect(int[][] arr, int col, int row) {
        //不能越界
        if (col < 0 || col >= arr.length
                || row < 0 || row > arr[0].length
                //必须是1 才进行感染
        ||arr[col][row]!=1) {
            return;
        }
        //修改为2
        arr[col][row] = 2;
        //向上感染
        infect(arr, col - 1, row);
        //向下感染
        infect(arr, col + 1, row);
        //向左
        infect(arr, col, row - 1);
        //向右
        infect(arr, col, row + 1);
    }

    public static void main(String[] args) {

        int[][] m1 = {
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 1, 1, 0, 1, 1, 1, 0},
                {0, 1, 1, 1, 0, 0, 0, 1, 0},
                {0, 1, 1, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0},
                {0, 0, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
        };
        System.out.println(countIslands(m1));
        int[][] m2={};
        System.out.println(m2.length);
        System.out.println(m2[0].length);
    }
}
